{--
    It is easily proved that no equilateral triangle exists with integral length sides 
    and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units.
        
    We shall define an almost equilateral triangle to be a triangle for which two sides are equal 
    and the third differs by no more than one unit.

    Find the sum of the perimeters of all almost equilateral triangles with integral 
    side lengths and area and whose perimeters do not exceed one billion (1_000_000_000).
    -}


-- ????????
-- runtime 15353.275 wallclock seconds.
-- Clearly outside the 1 minute limit
-- After mathematical expertise applied: runtime 0.144 wallclock seconds.

module examples.Euler94 where

import examples.EulerLib

main _ = do        
        print "Pell: ";  println (take 8 pell)
        print "Dreiecke Pell: "; println pTriangles
        print "Trans: "; println (take 8 transformed)     
        print "Dreiecke Trans: "; println tTriangles
        print "Solution: "
        println ((summe • map perimeter) pTriangles + (summe • map perimeter) tTriangles)
    where
        -- iterate f x =  [x, f x, f (f x), .... ]
        pell = iterate  (next (2,1))  (2,1)
            where 
                next (m0,n0) (m1,n1) = (m2,n2)
                    where 
                        m2 = m0*m1 + 3*n0*n1
                        n2 = n0*m1 +   m0*n1
        
        -- map f [a1, a2, a3, ... ] = [f a1, f a2, f a3, ...]                       
        transformed = map trans pell 
            where trans (m,n) = (m+2*n, n)
        
        triaX (m,n) = (2*x, z, z) where x = m*m - n*n; z = m*m + n*n
        triaY (m,n) = (2*y, z, z) where y = 2*m*n;     z = m*m + n*n 
                                    
        -- zu große Zahlen können überlaufen, dann ergeben sich negative Werte
        -- Wenn a größer als 333.333.334 ist, wird der Umfang zu groß                                                
        valid (a,_,_) = a > 0 && a <= 333_333_334
        perimeter (a,b,c) = a+b+c
        pTriangles = takeWhile valid (map triaX pell)
        tTriangles = takeWhile valid (map triaY transformed) 
                                                      

                                
        
    